package org.geekbang.time.mathbasicthought.lesson9_dynamic_programming;

/**
 * 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
 * <p>
 * 你可以认为每种硬币的数量是无限的。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/gaM7Ch
 */
public class Coin {
    static int coins[] = {2, 5, 7};
    static int amount = 27;

    public static void main(String[] args) {
        System.out.println(coinChange(coins, amount));
    }

    /*
    已知条件：
        1. 虽然我们不知道最优策略是什么，但是最优策略肯定是K枚硬币，且他们之和为 a1+a2+...+ak = 27
        2. 我们不关心前面的K-1枚硬币是怎么拼出27-ak的（可能有1种拼法，可能有100种拼法），而且我们现在还不知道ak和K，但是我们确定前面的硬币拼出了27-ak
        3. 因为是最优策略，所以拼出27-ak的硬币数一定是最少，否则这就不是最优策略了。换句话说，对于27来说，K为最少硬币数，那么对于27-ak来说，K-1为最少硬币数
    解题思路：
    1. 确定状态
        最后一步： 选择一枚硬币，在27-ak所需最少硬币的基础上，加1，硬币和为27。最后一枚硬币可能是coins中的任意一枚硬币
        子问题：   如何选择最少的硬币数量使之和为27-ak
        原问题：   如何选择最少的硬币数量使之和为27
        至此，子问题出现了，那么状态就可以确定了，为了简化子问题即状态的表达，我们设状态f(x)=最少用多少枚硬币拼出X
    2. 转移方程
        假如coins={2,5,7}，那么最优策略的最后一枚硬币ak只可能是2,5,7中的任意一个，所以f(27)有三种可能的K
        f(27) = f(27-2) + 1, f(27) = f(27-5) + 1, f(27) = f(27-7) + 1, 1指的是选择最后一枚硬币
        因此， 拼出和27的最优策略为 f(27) = min{f(27-2) + 1, f(27-5) + 1, f(27-7) + 1}
    3. 初始值和边界条件
        初始条件：f[0] = 0，用状态方程算不出来，但是方程需要一个起点才能开始计算，所以需要手工定义
        边界条件（x-2,x-5,x-7小于0怎么办？什么时候停下来？）：
            1. 如果不能拼出Y，就定义f[Y]=正无穷，比如f[-1]=f[-2]=...=正无穷
            2. Y=27时，即f[27]时可以停下来
    4. 计算顺序
        按照状态方程所需的顺序计算，比如计算f[27]需要f[27-2],f[27-5],f[27-7]，因此顺序为从小到大
     */
    public static int coinChange(int[] coins, int amount) {
        // 保存状态的数组
        int[] arr = new int[amount + 1];
        // 初始值
        arr[0] = 0;

        for (int i = 1; i < arr.length; i++) {
            // 边界条件
            arr[i] = Integer.MAX_VALUE;

            for (int coin : coins) {
                // 边界条件
                if ((i - coin >= 0) && arr[i - coin] != Integer.MAX_VALUE) {
                    arr[i] = Math.min(arr[i], arr[i - coin] + 1);
                }
            }
        }

        if (arr[amount] == Integer.MAX_VALUE)
            return -1;

        return arr[amount];
    }
}
